package 树;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/find-duplicate-subtrees/
 */
public class _652_寻找重复的子树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /*
        明确当前节点应该干什么？使用什么遍历顺序？
        当前根节点需要知道以自己为根的子树长什么样子，所以需要递归后序遍历，通过递归返回的结果才能直到自己子树长什么样子
        然后需要知道以其他节点为根的子树长什么样子？需要一个hashMap存，将多颗重复的子树删除，只保留一个
     */

    //存放结果集
    private List<TreeNode> res = new LinkedList<>();

    //存放所有子树以及出现的次数
    private HashMap<String,Integer> map = new HashMap<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return res;
    }

    //函数定义：输入一个根节点，返回以这个根节点的二叉树的序列化样子
    private String traverse(TreeNode root){
        if(root == null){
            return "?"; //为空就特殊字符处理
        }

        String left = traverse(root.left); //拿到左子树的序列化的样子
        String right = traverse(root.right); //拿到右子树序列化的样子

        //构造子树序列化的字符串,相当于知道了我自己的子树长啥样，我现在需要知道别的子树长啥样
        String subTree = left + "," + right + "," + root.val;

        //先去map寻找，是否有
        int cur = map.getOrDefault(subTree,0);

        if(cur == 1){
            //重复了走这个条件，只会添加到结果集一次
            res.add(root);
        }

        //结果在上次加1
        map.put(subTree,cur+1);
        return subTree;
    }
}
